Block ciphers are the most popular algorithms in use today for providing data privacy. Block ciphers with block size n and key size k can be viewed as a family of permutations on the set of all n-bit strings, indexed by k-bit long encryption keys and possessing certain properties. We denote by EK(x) the image of an n-bit string x under a permutation with index K from a family of permutations defined by block cipher E. We also call this image an encryption of plaintext with block cipher E under key K or, in short, a ciphertext corresponding to plaintext x. Since EK is a permutation, it has a reverse transformation, which we denote by DK. This reverse transformation can be used for recovering plaintext x given a corresponding ciphertext y=EK(x), by computing DK(y).
Some of the properties that are typically required of block ciphers are:
Simplicity of construction. Given key K, we should be able easily to construct EK and DK (algorithmic descriptions of the two transformations can be comfortably given in terms of an arbitrary k-bit string K). This is a very important property since complex constructions complicate analysis and may lead to flaws in implementation. We say that a block cipher is a symmetric encryption primitive to stress that knowledge of a single value K is sufficient for deriving both EK and DK.
Security. It is commonly accepted to consider a block cipher secure if, for a randomly chosen key K, it appears as a random permutation on the set of n-bit strings to any computationally bounded observer (i.e. who does not have an unlimited amount of processing power available) who does not know K and who can only see encryption of a certain number of plaintexts x of their choice. We can also say that a secure block cipher is a good pseudorandom permutation. (Obviously, no block cipher can be secure against a computationally unbounded attacker capable of running an exhaustive search for the unknown value of K.) We refer to [8] for an accurate treatment of the subject.
Good performance. Computing EK(x) and DK(y) should be fast for all K, x, y.
Other important practical aspects include reasonable memory requirements and efficiency of software and hardware implementations.
A number of known block ciphers will now be considered.
Data Encryption Standard (DES) has been in wide use since 1977. It is defined as FIPS in [9]. DES supports a 64-bit block size and a 56-bit key size. The design is extremely well studied and has traditionally been considered secure. DES is currently being phased out however because its key size is considered too small to withstand exhaustive search attacks on modem computers.
Triple DES was constructed by combining three DES functions in a specific way to retain good security properties of DES and to increase key size to render exhaustive search attacks infeasible. The algorithm definition can also be found in [9]. Higher security of triple DES comes at the expense of noticeably poorer performance. The cipher supports a 64-bit block size and a 168-bit key size.
Advanced Encryption Standard (AES) has recently been adopted as a new encryption standard [12]. The AES design received several years of thorough reviewing by many leading cryptography researchers. AES supports block sizes of 128, 192, and 256 bits and the same set of key sizes. The cipher allows for very efficient software and hardware implementations, thus addressing the most annoying problem of Triple DES.
In practice, most data units (including any typical file, database record, IP packet, or email message) which require to be encrypted are greater in length than the block size of the chosen cipher. This will require the application of the block cipher function multiple times. There are many ways of doing that and each is referred to as a “mode of operation”. The standardised modes of operation employing DES have been published in [10] and [1]. A more general version of the standard, published in [5], generalized four modes of DES to be applicable to a block cipher of any block size. The standard modes are known as Electronic Code Book (ECB), Cipher Block Chaining (CBC), Cipher Feedback (CFB), and Output Feedback (OFB).
According to The National Institute of Standards and Technology (NIST), with the advent of new symmetric key block ciphers such as AES, the currently used modes of operation need to be updated. NIST is accepting proposals for new modes and a second public workshop on the subject was held in August of 2001. The table of proposed modes that NIST has accepted for consideration can be found at http://csrc.nist.gov/encryption/modes/proposedmodes/.
The reason why NIST and others believe that a number of different modes of operation are necessary is that it is probably impossible to derive a single mode of operation that would be the ideal choice for all applications, protocols, and settings. Which mode is the best for a suitable situation depends heavily on the particular set of requirements that need to be satisfied. Below, we list some of the properties that one always or usually requires from a mode of operation:
(a) Security. This is always the most important property but its exact meaning may vary depending on what it is possible to achieve in a particular setting. We usually assume that our underlying block cipher is secure and that the key size k is chosen so that an exhaustive key search is computationally infeasible. However, regardless of the cryptographic strength of the block cipher, ciphertext produced by using some modes of operation may leak information about the corresponding plaintext as we encrypt many plaintext blocks under the same key, or encrypt plaintexts having identical parts under the same key. The strongest notion of security that one can hope to achieve in practice is so-called semantic security: any non-trivial computational information that can be derived from encryption of a message EK(M), should also be computable without EK(M). In certain situations, it is impossible to achieve semantic security, and then the goal is to leak the minimum possible amount of information.
We note that the best argument in favor of the security of a particular mode is a tight reduction from the security of the mode to the security of the underlying cipher. For that, we need to show that a successful attack on the mode of operation gives us almost an equally successful attack on the underlying cipher. Thus, our belief in the security of, e.g. AES, can be translated into trust of a mode of operation of AES whose security is tightly reduced to the security of its underlying cipher. This approach was originally introduced and developed in [2].
In many cases, it is desirable that the mode of our choice provides not only privacy or confidentiality of messages, but also authenticity. This property guarantees that the only feasible way to produce a valid ciphertext is to apply the encryption function EK to some message M, which requires knowledge of key K. Unfortunately, it is sometimes difficult to efficiently achieve authenticity in practice, for example, due to the specific ways used to access information.
(b) Efficiency. It is obvious that to encrypt an l-bit long message, we need to apply the underlying block cipher function at least [l/n] times, where n is the block size of our cipher. Any additional operations that a particular mode of operation involves are considered as an overhead that we want to minimize.
(c) Random access. Some modes allow encrypting and decrypting of any given block of the data in an arbitrary message without processing any other portions of the message.
(c) Parallelizability. Can we use the advantage of a multiprocessor machine and run the encryption and decryption computations in parallel?
(d) Keying material. Some modes require two independent block cipher keys, which leads to additional key generation operations, a need for extra storage space or extra bits in communication.
(e) Counter/IV/Nonce requirements. Almost all modes make use of certain additional values together with block cipher key(s). In certain cases, such values must be generated at random or may not be reused with the same block cipher key to achieve the required security goals. Limitations of this sort may rule out some modes for certain applications.
(f) Pre-processing capability. Can some part of computations be done prior to knowing the message that needs to be processed? In certain settings, this may save us valuable time, whilst in other cases this may be practically irrelevant.
There will now be described several popular modes of operation and the properties they possess.
ECB mode (also called the native mode). To encrypt a message of arbitrary length, we split it into consecutive n-bit blocks M1, M2, M3, . . . and apply EK separately to each block. The resulting encrypted message will be EK(M1), EK(M2), EK(M3), . . . In general, the i-th ciphertext block Ci is computed as Ci=EK(Mi). The decryption formula is straightforward: Mi=DK(Ci).
(a) Encryption in ECB mode maps identical blocks in plaintext to identical blocks in ciphertext, which obviously leaks some information about plaintext. Even worse, if a message contains significant redundancy and is sufficiently long, the attacker may get a chance to run statistical analysis on the ciphertext and recover some portions of the plaintext. So, in some cases, security provided by ECB is unacceptably weak.
(b) It is evident that ECB achieves perfect efficiency as it does not involve any computational overhead.
(c) Since all blocks are processed individually, ECB provides random access to data. That is to say that, working with a particular block, we do not have to process any other blocks.
(d) ECB is perfectly parallelizable.
(e) Requires a single block cipher key.
(f) Does not use any additional values.
(g) No pre-processing is possible. However, this is not a concern due to the processing properties (b) and (d).
Note also that plaintext can be easily manipulated by removing, repeating, or interchanging ECB-encrypted blocks.
To conclude, ECB may be a good choice if all we need to do is protect very short pieces of data or nearly random data. A typical use case for ECB is the protection of randomly generated keys and other security parameters.
CBC mode. In this mode the exclusive-or (XOR) operation is applied to each plaintext block and the previous ciphertext block, and the result is then encrypted. An n-bit initialization vector IV is used to encrypt the very first block. To encrypt our message we successively computeC1=EK(M1 XOR IV)C2=EK(M2 XOR C1)Letting C0=IV, we have Ci=EK(Mi XOR Ci−1) as a general formula. Decryption is given by Mi=DK(Ci) XOR Ci−1.
It can be seen that encryption of the i-th block depends on all previous plaintext blocks.
(a) CBC hides patterns in plaintext. In fact, it can be proved that there is a reduction of security of CBC mode to security of the underlying cipher provided that IV is chosen at random [2]. Still, some theoretical problems exist for CBC. For example, if one observes in a ciphertext that Ci=Cj, it immediately follows that Mi XOR Mj=Ci−1 XOR Cj−1, where the right-hand side of the equation is known. This is called the birthday or matching ciphertext attack. Of course, if the underlying cipher is good in the sense of pseudorandom permutation and its block size is sufficiently large, the probability of encountering two identical blocks in ciphertext is very low. By itself, CBC does not provide authenticity.
(b) The computational overhead of CBC is just a single XOR operation per block encryption/decryption, so its efficiency is very good.
c) CBC provides random read access to encrypted data, that is, to decrypt the i-th lock, we do not need to process any other blocks. However, any change to Mi would require re-encryption of all blocks with indexes greater than i. We say that CBC does not support random write access to encrypted data.
(d) CBC cannot be parallelized. (In fact, there is a method called interleaving which allows for encrypting of t blocks in parallel at the expense of generation/maintaining t initialization vectors.)
(e) Requires a single block cipher key.
(f) Uses an initialization vector that must be generated at random. (It is actually sufficient to require that we never reuse a value of S for a particular key K and use IV=EK(S).)
(g) No pre-processing is possible.
It can be seen that CBC is quite a good choice unless we need random write access, authenticity, or convenient parallelizability. Complemented with appropriate authentication methods, CBC is successfully used in numerous applications for encrypting email messages, IP packets, etc.
Counter mode. This mode has been proposed to NIST for consideration [7]. Although it is not a standard mode of operation, it has found use in certain applications and protocols. In this mode, a block cipher is used to generate a bit stream that is then XORed with plaintext in the following way:C1=M1 XOR EK(T)C2=M2 XOR EK(T+1 mod 2n)where T is an n-bit string used as an initial value of counter, and the mod2n operation is used to ensure that the argument to the encryption function is always an n-bit value. So, the formula is:Ci=Mi XOR EK((T+i−1)mod 2n)The decryption formula is identical:Mi=Ci XOR EK((T+i−1)mod 2n).
We see that encryption of a block depends on its offset in the message and does not depend on the values of any other blocks. We also note that encryption and decryption operations are identical which allows savings on the implementation code size and required memory.
(a) The security of Counter mode can be reduced to the security of the underlying cipher provided that values of counter (T+i−1) are never reused with the same key K [2]. (See also point (f) below)
By itself, the mode does not provide authenticity.
(b) The Computational overhead of Counter mode is also a single XOR operation per block encryption/decryption as in CBC, plus updating the value of T, so its efficiency is very good.
(c) Counter mode provides random read and write access to encrypted data.
(d) It is perfectly parallelizable.
(e) Requires a single block cipher key.
(f) Uses an initial counter value that may not be reused with the same key K. Moreover, if we encrypt two messages under the same key, none of the values of counter used for one of them may be equal to any counter value used in encryption of the other message. (If the same value of counter is used for encrypting two distinct blocks Mi and M′j under the same key, the attacker immediately obtains the value of Mi XOR M′j, which is unacceptable under any reasonable definition of security.) There are no other requirements for the initial counter value generation method. In particular, initial values do not have to be generated at random.
(g) Counter mode is ideal in the sense of pre-processing. The bit stream used in the mode can be computed at any time as this does not require a knowledge of the message to be encrypted or decrypted.
In many respects, Counter mode is superior to CBC mode. However, this mode cannot be used in applications where it is impossible to provide non-intersecting sets of counter values for distinct messages encrypted under the same key.
We complete this section by defining OFB and CFB modes which are the two remaining standard modes. These modes resemble Counter mode in the sense that they also convert block ciphers into key stream generators.
OFB mode. Pick up IV at random and let Z0=IV. The key stream is given by the recurrence Zi=EK(Zi−1). Then, as in Counter mode, Ci=Mi XOR Zi and Mi=Ci XOR Zi.
CFB mode. Pick up TV at random and let C0=IV. The key stream is given by the relation Zi=EK(Ci−1). To encrypt and decrypt, we again use Ci=Mi XOR Zi and Mi=Ci XOR Zi respectively.